package _go

/*64. 最小路径和
难度
中等

1049

收藏

分享
切换为英文
接收动态
反馈
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。



示例 1：


输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12


提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100*/

func minPathSum(grid [][]int) int {
	m := len(grid)
	if m == 0 {
		return 0
	}
	n := len(grid[0])
	if n == 0 {
		return 0
	}
	//可以申请一个单独的内存  也可以直接用原来的内存就够了
	// dp := make([][]int,m)

	// for i:=0;i<m;i++{
	//     dpj := make([]int, n)
	//     dp[i] = dpj
	// }

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if i == 0 && j == 0 {
				grid[0][0] = grid[0][0]
			} else if i == 0 {
				grid[0][j] = grid[0][j-1] + grid[0][j]
			} else if j == 0 {
				grid[i][0] = grid[i-1][0] + grid[i][0]
			} else {
				//主要逻辑在这里  最小路径的和 等于前一个或者上一个其中那个小  然后加上现在的值就是当前的做小路径和
				grid[i][j] = min(grid[i][j-1], grid[i-1][j]) + grid[i][j]
			}
		}
	}
	// fmt.Printf("sdf %+v \n",dp)
	return grid[m-1][n-1]
}
func min(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
